Subject: pacing proposal

From: [email-masked]
Date: Thu, 22 Jul 93 17:54:34 EDT

On the 13th, Shannon requested complete informal proposals by the 23rd.
I will be on vacation tomorrow and next week so I thought I had better
lay out my current thoughts on what we might do.  I feel a bit uncomfor-
table doing so because I haven't prototyped this yet (although the ingre-
dients have all been used before).  But hey, now all the holes will be
discovered while I'm away!  Seriously, I'm sure this will be a group
effort as we each look at these from the perspective of our products'
internal design.  I reserve the right to suggest major modifications
myself, as I get back comments (including within IBM), think about it
more, and try it out.

As I've worked on this, I've gotten further away from the original
Wind/Kushi model and closer to what was done for APPN session-level
pacing.  I tended this way as I tried to think about the needs of the
person designing receive buffer management.   If people disagree, I'm
sure everyone will let me know.  I'm not stuck on this and can back off
if people like the bit-oriented model better.  This is just current
thinking.

This does not address the UI-frame balancing problem, just LLC2
connections/circuits.  The description is informal and undoubtedly
incomplete.  I can beef it up later if people feel the direction is
right.
-------------------------------------------------------------------

Flags/fields in the short ("information header"):
- Pacing Request Indicator (PREQ) - 1 bit
- Request Larger Window Indicator (RLWI) - 1 bit

New SSP message types:
IPM
- can be of type SOLICITED, UNSOLICITED, or RESET ACKNOWLEDGEMENT
- can have scope of either CIRCUIT or TRANSPORT CONNECTION
- contains Next Window Size (NWS) - 2 bytes

Comments on formats -
The NWS replaces the use of bits DWSI, IWSI, and CWI.  I don't think
DCFI is needed in this algorithm.  I prefer that the receiver be
able to set an explicit value for the next window size because:
  - it gives the receiver much better control over the value
  - it's easier to understand and work with

The IPM fields follow the 16-byte information message header.

ENTERBUSY and EXITBUSY are not part of this proposal.  Shutting off
flow on a circuit is done with NWS=0.  Since the 6611 uses __BUSY
signals in certain connect sequences, they may need to become part of
the standard DLSw connect sequences, but that is another discussion.
These signals are not to be used for normal connection flow control.

Function:
Pacing is done on a circuit basis only, in both directions independently.
The pacing receiver controls via a sliding cumulative window how many
frames a sender may put on a transport connection, for a given circuit.
At what point a data link should be RNRed is an implementation issue
for the router and is not specified by this pacing architecture.
Pacing is applied only to I-frames, not UI-frames flowing on the same
circuit.

The sender sets PREQ in the first frame of every window.  In the normal
case, it will continue to send the full window's worth of frames before
it must stop and await a pacing response.  If the sender reaches the
end of a window, and has more data to send at the time the solicited
pacing response comes back, it sets RLWI along with PREQ in the next
pacing request.  RLWI can be set only in pacing requests.  When a pacing
response is received, the NWS is added to the current remaining window
size to reach a new window size.

The initial pacing window size for a circuit is 2, allowing some chance
RLWI will not be set in the next pacing request.

In normal operation, the receiver receives I-frames and looks for
a frame with PREQ set.  When it sees one, it determines based on
implementation-dependent conditions the NWS to grant the sender and
when to send the pacing response (it could be withheld).  The receiver
has complete control over the window sizes it grants, and is not
required to pre-allocate or guarantee buffer space for all the outstand-
ing windows.  The receiver can get insight from the RLWI bit about how
the sender is operating, and the receiver should honor the request if
possible, but is not obligated to do so.

Pacing responses are always sent as IPMs and are not piggy-backed.  They
are sent at higher priority than other information flowing in the same
direction (with TCP, as urgent data).  The responses discussed so far
are SOLICITED and have scope CIRCUIT.

To respond quickly to congestion (or reflect a received RNR), the
pacing receiver may send an IPM of type RESET.  The NWS of a RESET IPM
is always zero.  The pacing sender (receiver of the RESET) must
immediately stop sending I-frames and set its current window size to
zero.  It also sends a RESET ACK IPM at normal priority, so the
pacing receiver can determine the end of queued data.  The RESET ACK
is an implicit pacing request, so when the pacing receiver decides
to reopen the window, it sends a SOLICITED IPM with a new non-zero
window size.  All these IPMs have scope CIRCUIT.

When a receiving router wishes to slam every circuit on a particular
transport connection, it may send a RESET IPM with scope TRANSPORT
CONNECTION.  The pacing sender must stop sending I-frames on all circuits
on that TC and set their current window sizes to zero.  It also sends
a RESET ACK IPM with scope TRANSPORT CONNECTION, at normal priority.
Circuits must be restarted on an individual basis.  There is no normal
pacing with window counts, etc., on a transport connection basis;  a
SOLICITED IPM may never have scope TRANSPORT CONNECTION.

Commentary:
- About urgent data - I don't have particular scenarios, but some of
  the flow control gurus here say it's critical to have pacing responses
  flow faster than normal data, otherwise you can have deadlock problems.
  My TCP books suggest maybe urgent data is the solution, but I have no
  practical experience with it - perhaps someone out there can tell me
  if this will work.
- Reasons for not piggy-backing pacing responses are:  so it can go
  in an out-of-band mode, and so you don't have to worry about how long
  to wait before sending as isolated.  These are very short messages.
- RLWI can be tricky, in that there are scenarios where honoring the
  request could make things worse.  Consider IP congestion where the
  pacing receiver buffer pools are looking good.  RLWI may be set
  repeatedly but increasing the window size makes the congestion worse.
  This is where the sending node's TCP should back up and that node
  should start RNRing links feeding the congestion.  I considered not
  having RLWI but I figured it was better to give the receiver some
  information about the sender's state than none.
- Reasons for this scheme versus the more bit-oriented one:
   - I think it gives the receiver more options for buffer management
     when it can explicitly control the window size
   - It keeps window size information more controlled than when the
     IWSI and DWSI bits can be set on any frame (you have a better
     idea of where the partner is)
   - It adds a TC-level mechanism, which people seemed to want
- Justification for RESET ACK (potentially two WAN frames per rcvd RNR):
   - It makes the state machine much cleaner to know that the other
     guy is done sending, allows more predictable operation during crises.
     Since we're so high up the protocol stack, there can be a lot of
     queueing underneath.
   - The handshake can cut down on WAN traffic if you have a station
     rapidly going RNR/RR (you can have only one UNSOLICITED IPM out-
     standing).  Of course, this can be done with timers also.
   - You just freed up WAN bandwidth by stopping I-frame traffic, this
     does not add much.  Plus the TC-level IPM can reduce the need
     for lots of these flows.
   - WAN outrunning the LAN station will be much less frequent than
     the reverse.
- Maybe the initial window size should be 1 so things start more
  slowly when there are lots of new links to the same destination.

OK, folks, let me know what you think.  Maybe a consensus (like "let's
kill this guy") will have emerged by the time I get back!

Thanks,
Peter Gayek

---

From: Bernard Brady <[email-masked]>
Date: Fri, 23 Jul 93 10:58:19 EDT

Peter,

I like what you have written except in the case of the RLWI. 

>In normal operation, the receiver receives I-frames and looks for a
>frame with PREQ set.  When it sees one, it determines based on
>required to pre-allocate or guarantee buffer space for all the
>outstand- ing windows.  The receiver can get insight from the RLWI bit
>about how the sender is operating, and the receiver should honor the
>request if possible, but is not obligated to do so.

I think that the receiver should be able to inform the sender that it 
has accepted the fact of going to a larger window size.   By what I read
the receiver is forced to accept when it sends a  pacing response.  This
is caused by the sender automatically upping the window size when it
receives the pacing response.   I  think we should define a Accept
Larger Window Indicator (ALWI) - 1 bit in the pacing response.  When a
pacing response is received with the ALWI set, the NWS is added to the
current remaining window size to reach a new window size.  In the case
where a RLWI is outstanding and a pacing response is received without
the ALWI set then the window size is left unchanged by the sender. By
witholding pacing data flow is stopped.  By immplementing ALWI the
receiver is not accepting the NWS but is  allowing data to flow. 
Getting data through slower is better than no data at all.

In the write up I think we should replace the word "slam" with flow
block, most systems come standard with ABS installed these days.

Bernie Brady

Bernie Brady

---

From: [email-masked] (Anand Subramaniam)
Date: Fri, 30 Jul 93 17:29:53 PDT

Hi,

 >window size.  All these IPMs have scope CIRCUIT.

   I tend to agree with Shannon. Is it a good idea to respond to congestion
   right away(RNR)? I think the pacing receiver must on receipt of RNR must
   decide if the receive window is full so that if it is capable of buffering
   up more frames up to the window it should so that if the RNR condition 
   happens to be a fleeting one, it would go unnoticed by the sender. However 
   once the receive window is full, the receiver could hold back the response 
   or send the response with NWS=0. 

   If the receive window is closed, how long should the sender wait before
   requesting the receiver to open up the window. Do you plan to have anything
   like a window timer?

   What will happen if the receiver had previously advertised a larger window
   but later decides to reduce the window? How does this work in your proposed
   scheme? From what I understand, NWS is used to increment the window or
   close the window.

Urgent Data in TCP
------------------

In TCP, the presence of urgent data in the data stream is indicated to the TCP
application. This means that the application needs to read all the data in
front of the urgent data first before getting to the urgent data. Thus urgent
data does not "bypass" normal data but only could expedite the reading of the
received data by the receiving application. So I am not sure if we could use
urgent data to send pacing messages.

Flow Control in TCP
-------------------

We need address the case where the TCP gets congested because of a "bad guy"
and this means that the others will suffer. In this case even the pacing
messages cannot go across and data could get potentially stuck on the DLSw
send queue. So  in this case window might not slide for some time. So I think
it might a good idea to consider having a window update timer.

--andy 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| UUCP:  {ames,apple,sun,mtxinu}!excelan!andy         (Anand Subramaniam) |
| INTERNET:  [email-masked]                          Ph : (408)-473-8413 |
| " Now and then I go off in to my own little world; But they know me     |
|   there"                                                                |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+